1. Technical Field of the Invention
The present invention relates generally to optical routing and scheduling of data packets, and more specifically to an optical routing and scheduling of data packets employing a void filling algorithm and fiber delay lines (FDLs) as an optical buffer.
2. Discussion of the Related Art
One of the major trends in networking in late 1990""s has been a relentless growth in demand for bandwidth in both enterprise and service provider networks. Driving the need for more bandwidth is a combination of factors. More users are connecting as the commercial Internet offers a new online experience for consumers. Internet computing applications, including multi-tier distributed databases, interactive multimedia communication, and electronic commerce rely on the network and demand network resources. A new generation of high-speed Internet access is emerging to meet bandwidth demands and further amplify core bandwidth requirements.
At the same time, competitive pressures make it imperative that networking costs be reduced even as the demand for capacity and new services increases. Successful companies are constantly on the lookout for new technologies which can provide a competitive edge and increase their cost effectiveness.
Optical networking has emerged as a solution to the bandwidth crunch. In particular, one new optical technologyxe2x80x94Dense Wavelength Division Multiplexing (DWDM)xe2x80x94promises to increase the capacity and performance of existing fiber optic backbones. DWDM offers a capacity upgrade solution with greater scalability and lower cost than available alternatives.
Wavelength Division Multiplexing (WDM) is a technique for increasing the information-carrying capacity of optical fiber by transmitting multiple signals simultaneously at different wavelengths (or xe2x80x9ccolorsxe2x80x9d) on the same fiber. In effect, WDM converts a single fiber into multiple xe2x80x9cvirtual fibers,xe2x80x9d each driven independently at a different wavelength. Systems with more than a small number of channels (two or three) are considered Dense WDM (DWDM) systems. Nearly all DWDM systems operate across a range of wavelengths in the 1550 nm low-attenuation window.
A DWDM system generally includes optical transmitters (lasers), an optical multiplexer and an demultiplexer, optical amplifiers and optical receivers. DWDM systems use high resolution, or narrowband, lasers transmitting in the 1550 nm wavelength band.
The optical multiplexer combines the transmit signals at different wavelengths onto a single optical fiber, and the demultiplexer separates the combined signal into its component wavelengths at the receiver. Several technologies are currently used for optical multiplexing and demultiplexing, including thin-film dielectric filters and various types of optical gratings. Some (de)multiplexers are constructed as completely passive devices, meaning they require no electrical input. Passive optical (de)multiplexers behave essentially like very high precision prisms to combine and separate individual colors of the WDM signal.
The optical receiver is responsible for detecting an incoming lightwave signal and converting it to an appropriate electronic signal for processing by the receiving device. Optical receivers are very often wideband devices able to detect light over a relatively wide range of wavelengths from about 1280-1580 nm. This is the reason why some seemingly incompatible devices can actually inter-operate. For instance, directly connecting two otherwise compatible network interfaces with different transmitter wavelengths is usually not a problem, even though one end may be transmitting at 1310 nm and the other at 1550 nm.
An additional benefit of the optical amplifier is that as a strictly optical device, it is a protocol- and bit rate-independent device. In other words, an optical amplifier operates the same way regardless of the framing or bit rate of optical signals. This allows a great deal of flexibility in that an optically amplified link can support any combination of protocols (e.g. ATM, SONET, Gigabit Ethernet, PPP) at any bit rate up to a maximum design limit.
With the deployment of DWDM optical fiber transmission systems to accommodate the ever increasing demand for bandwidth, driven by Internet applications, routers/switches are still likely to be the bottleneck of the next generation of Internet backbones. Using the DWDM technology, one can already achieve the transmission capacity of 320 Gbps per fiber commercially. The need for extremely high capacity routers, in the range of one terabits per second (Tbps) and beyond, is expected in the near future.
Optical burst switching (OBS) is an attractive technology in building tera-bit optical routers and realizing the Internet Protocol (IP) over dense wavelength division multiplexing (DWDM). An intrinsic feature of OBS is the separate transmission and switching of data bursts 150 (payload) and their headers 155 (called burst header packets (BHP)) on data and control channels/wavelengths, respectively. Due to the lack of an optical RAM (random access memory), fiber delay lines (FDLs) are used in optical routers to resolve burst conflicts on outbound data channels. In a simplified optical router architecture with N input fibers and N output fibers each fiber has one data channel group (DCG) of (Kxe2x88x921) channels and one control channel group (CCG) of one channel.
For optical routers using FDL buffering, there is a scheduler for each outbound DCG which schedules the arriving data bursts 150 that are to be routed to the same outbound DCG. The scheduler is a key component in the switch control unit. Any channel scheduling algorithm used in the scheduler will directly affect the router performance in terms of throughput and burst loss ratio. The prior art has not produced channel scheduling algorithms capable of providing acceptable throughput and burst loss ratio.
What is needed are sophisticated channel scheduling algorithms incorporating void filling in order to achieve the desired router performance. For any scheduling algorithm with void filling, each scheduler needs to keep track of the busy/idle periods of every data channel of its associated outbound DCG. The scheduler searches for an eligible void/gap when scheduling an arriving data burst. The search has to be done very quickly, e.g., in the range of a few hundred nanoseconds (say 100-300 ns), as the data burst is transmitted at the speed of light. As the number of channels handled by the scheduler increases, so does the complexity of the scheduler.
A scheduler that has to maintain the hardware implementation of a scheduling algorithm with void filling is a technically challenging endeavor, given the stringent real-time requirements and the state information of each data channel.
Various channel scheduling algorithms with and without void filling have been proposed such as the Latest Available Unused Channel (LAUC) algorithm, (also called the Horizon algorithm) and the Latest Available Unused Channel with Void Filling (LAUC-VF) algorithm (and variations on that theme), and other void filling scheduling algorithms. In terms of router performance (burst loss ratio) simulation studies have shown that the LAUC-VF is probably one of the best among all the scheduling algorithms. Despite the studies and the need for such algorithms, no hardware implementation design is available to implement these algorithms.
Accordingly the present invention provides a scheduling algorithm incorporating void filling and a hardware implementation design capable of implementing the algorithm wherein the desired performance is capable of scheduling a data packet in no more than a few hundred nanoseconds.
The present invention has been made in view of the above circumstances and has as an object to employ a special-purpose parallel processing architecture in the design of the scheduler to meet the stringent real-time requirements. Specifically, the present invention contemplates the use of an associative memory to store the state information of channels and to use associative processor arrays to implement void/gap searches and channel state information updates. The use of the associative processor arrays to implement the channel scheduler provides several advantages. One advantage of the present invention is the state information for a DCG is limited so that an associative memory of a rather small size is adequate. Another advantage is the search and update of the state information of a DCG, which is represented by the relative times of a set of events, is carried out in parallel.
The implementation of the LAUC-VF algorithm or any of the other viable algorithms, requires that the channel state information be frequently updated to reflect the change in time. To solve this problem, the present invention employs the use of relative timing verses absolute timing for representing channel state information. This is achieved by taking a reference point of the relative time, such as at the time the scheduler starts to process a BHP. At each new reference point the state information of all the channels of a DCG are updated simultaneously.
Associative processors PG, PM and PL are used to store all the voids, channel unscheduled times and delay times of FDLs, respectively. Search and update functions are also provided and substantially enhance the utility of the algorithm of the present invention. A control processor (CP) coordinates the operations of the processors PG, PM and PL.
In processor PG, voids are stored in a given order according to their starting times. Similarly, in processors PM and PL, the channel unscheduled times and delay times of FDLs are also stored in a given order. Searching for a void can easily be performed by one operation called xe2x80x9cParallel Double-Comparand Searchxe2x80x9d. Inserting new voids into the PG processor is performed by the xe2x80x9cBipartition Shift-Upxe2x80x9d and xe2x80x9cBipartition Shift-Downxe2x80x9d operations. Processors PG and PM are first used together to find the latest available unused channel without using any FDL buffer. In case FDL are used processor PL will be involved to determine which FDL buffer will be used.
The present invention contemplates the use of a special-purpose parallel processing architecture in the design of schedulers in optical routers, by providing design methodologies for implementing a class of scheduling algorithms with and without void filling.
A further aspect of the present invention is to provide a system for scheduling of data packets in an optical router operating pursuant to an algorithm capable of selecting a suitable outbound channel in real time.
Additional aspects and advantages of the invention will be set forth in part in the description which follows, and in part that will be obvious from the description, or may be learned by practice of the invention. These aspects and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims.
To achieve the aspects of the present invention and in accordance with the purpose of the invention, as embodied and broadly described herein, an aspect of the invention can be characterized as a method for implementing channel scheduling algorithms in an optical router, the method including the steps of determining availability of outbound data channels capable of carrying a data packet of duration B and selecting one channel from available data channels. The algorithm further assigns the data packet to the selected channel and updates state information of the selected data channel, wherein if no data channel is available to carry the data packet the data packet is dropped. The algorithm also is capable of determining whether a time delay L can be introduced to shift the arrival time of the data packet via a fiber delay line (FDL), from t to (t+L) to avoid the dropping of the data packet. If such a delay L is available, the algorithm assigns the data packet a delay time equal to L and assign s the appropriate outbound data channel.
The assigning of a channel further includes selecting a fiber and a wavelength from the outbound data channel group to transmit the data packet wherein the data packet may be of a fixed or variable length.
A further aspect of the present invention can be characterized as a system for implementing channel scheduling algorithms in an optical router. The system includes a scheduler, operating pursuant to an algorithm. The scheduler is capable of determining availability of outbound data channels capable of carrying a data packet of duration B and selecting one channel from available data channels. The system then assigns the data packet to the selected channel and updates state information of the selected data channel, but if no data channel is available to carry the data packet the data packet is dropped.
A still further aspect of the invention can be characterized as an apparatus for implementing channel scheduling algorithms in an optical router, the apparatus including means for determining the availability of outbound data channel capable of carrying a data packet of duration B and selecting one channel from the available data channels. The apparatus also includes means for assigning the data packet to the selected channel and means for updating state information of the selected data channel, but if no data channel is available to carry the data packet, the packet is dropped. The means for determining the availability of an outbound channel includes the use of associative processors PG and PM to store and search voids/gaps and channel unscheduled time for which a channel is free, respectively. PG is capable of storing the set of voids/gaps and the corresponding channels and to conduct of parallel search of the set of voids gaps for an available void/gap which is capable of accommodating a data packet. PM is capable of storing a set of channel unscheduled times from which a channel is free and the corresponding channels and to conduct a parallel search for an available unscheduled time for which a channel is free.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.